package q710_BlackList;

import java.util.*;

public class Solution_2 {
    Map<Integer, Integer> b2w;
    Random random;
    int bound;

    /*
    题目中已经说明了黑名单的长度不超过数组的长度 所以我们可以使用哈希映射的方式
    考虑一个问题 如果黑名单中的数字是连续的 并且集中在最后一端
    例如假设黑名单的长度是m 那么就是 (n - m, n) 最后一段是黑名单中的数字 而 (0, n - m)就是白名单中的数字
    此时我们只需要直接从白名单中随机生成一个数字返回即可

    但实际上黑名单中的数字是散列的 因此有这样的一种方法：
    首先对于黑名单的长度是m时，在 (n - m, n) 这一段中 本来就在黑名单中的数字 我们将其加入到一个set中
    然后考虑将(0, n - m)中黑名单的数字 依次映射到(n - m, n)中正常的数字中
    通过这样的方式 我们如果在pick方法中随机抽取到了(0, n - m)中黑名单的数字 只需要利用map映射取出其对应(n - m, n)中正常的数字即可

     */
    public Solution_2(int n, int[] blacklist) {
        b2w = new HashMap<>();
        random = new Random();
        int m = blacklist.length;
        bound = n - m;
        Set<Integer> black = new HashSet<>();
        for (int b : blacklist) {
            if (b >= bound) {
                black.add(b);
            }
        }

        int w = bound;
        for (int b : blacklist) {
            if (b < bound) {
                while (black.contains(w)) {
                    ++w;
                }
                b2w.put(b, w);
                ++w;
            }
        }
    }

    public int pick() {
        int x = random.nextInt(bound);
        return b2w.getOrDefault(x, x);
    }

}
